package com.ryujung.linked_list.leetCode_206;

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(final int x) {
        val = x;
    }

    @Override
    public String toString() {
        return "ListNode [next=" + next + ", val=" + val + "]";
    }

}

/**
 * Reverse a singly linked list.反转一个链表
 * 
 * Input: 1->2->3->4->5->NULL; Output:5->4->3->2->1->NULL;
 * 
 * 思路: 双指针法,将所有的Node的next元素都指向自己前一个元素即 
 * 1->2->3->4->5 变为 1<-2<-3<-4<-5
 * 
 * 1.创建两个指针ListNode,pre和cur,cur初始为head 
 * 2.让cur.next指向pre 3.两个同时后移一个元素
 */
class Test {
    public static ListNode reverseList(ListNode head) {
        // 让每个当前节点指向上一个节点
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            // 临时保存head节点原来的的next
            ListNode nextNode = cur.next;

            // 改变当前元素的指向
            cur.next = pre;

            // 两个指针同时下移
            pre = cur;
            cur = nextNode;
        }
        return pre;
    }
    
    /**
     * recursive version
     * 思路:
     * 1.递归找到最后一个元素(指向null的元素) 
     */
    public static ListNode reverseList2(ListNode head) {
        //末尾的元素,直接返回
        if(head.next==null || head==null){
            return head;
        }
        
        ListNode p = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
    
    static String toString(ListNode head) {
        ListNode temp = head;
        StringBuilder sb = new StringBuilder();
        if (head != null) {
            while (temp.next != null) {

                sb.append(temp.val + ",");
                temp = temp.next;
            }
            sb.append(temp.val);
            return sb.toString();
        }
        return null;
    }

    public static void main(final String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        System.out.println(toString(n1));

        ListNode res = reverseList2(n1);

        System.out.println(toString(res));
    }
}